/*
318. Maximum Product of Word Lengths
 Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words. 
*/
#include <math.h>
#include <string>
#include <vector>


using namespace std;
/**
 * 解法1：
 * 用mask来判断两个字符串是否有相同的字符
 * 使用c=++11特性的变长数组
 * 减枝时去掉空字符串
 * 如果字符串按长度排序的，还可以在ret=m*n（m>n），之后循环至n时退出循环
 */
class Solution
{
public:
    int maxProduct(vector<string> &words)
    {
        if(words.size() <= 1) return 0;
        int n = words.size();
        int a[n] = {0};
        int sizes[n];
        int m = 0;
        for(auto &word : words) {
            if(word.size() == 0) continue;
            sizes[m] = word.size();
            for(auto &ch : word) {
                a[m] |= 1 << (ch - 'a');
            }
            m++;
        }
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) {
                if(0 == (a[i] & a[j])) {
                    ret = max(sizes[i] * sizes[j], ret);
                }
            }
        }
        return ret;
    }
};
/**
 * 解法2,错误：
 *  * 如果某一次循环后，ret=0，说明这个字符串和后面的都重复，退出循环
*/
class Solution
{
public:
    int maxProduct(vector<string> &words)
    {
        if(words.size() <= 1) return 0;
        int n = words.size();
        int a[n] = {0};
        int sizes[n];
        int m = 0;
        for(auto &word : words) {
            if(word.size() == 0) continue;
            sizes[m] = word.size();
            for(auto &ch : word) {
                a[m] |= 1 << (ch - 'a');
            }
            m++;
        }
        int ret = 0;
        for(int i = 0; i < m; i++) {
            int tmp = 0;
            for(int j = i + 1; j < m; j++) {
                if(0 == (a[i] & a[j])) {
                    tmp = max(sizes[i] * sizes[j], tmp);
                }
            }
            if(tmp == 0) break;
            ret = max(tmp, ret);
        }
        return ret;
    }
};